#include <iostream>
#include <vector>
#include "../utils.h"

// 改变原数组
int duplicate(std::vector<int> input) {
  auto len = input.size();
  for (auto i = 0; i < len; ++i) {
    if (input[i] < 0 || input[i] > len - 2) {
      std::cout << "invalid input.";
    }
  }

  auto swap = [&] (int i, int j) {
    auto temp = input[i];
    input[i] = input[j];
    input[j] = temp;
  };

  for (auto i = 0; i < len; ++i) {
    while (input[i] != i) {
      if (input[i] == input[input[i]]) {
        return input[i];
      }
      swap(i, input[i]);
    }
  }
  std::cout << "null.";
  return 0;
}

// 不改变原数组
int duplicate_II(const std::vector<int> &input) {
  auto len = input.size();
  for (auto i = 0; i < len; i++) {
    if (input[i] < 0 || input[i] > len - 2) {
      std::cout << "invalid input.";
    }
  }

  auto get_count = [&](const int &start, const int &end) {
    int count = 0;
    for (auto i = 0; i < len; ++i) {
      if (input[i] >= start && input[i] <= end) {
        ++count;
      }
    }
    return count;
  };

  int start = 0;
  int end = len - 2;
  while (start <= end) {
    int middle = start + ((end - start) >> 1);
    int count = get_count(start, middle);
    if (middle == start && count > 1) {
      return start;
    }

    if (count > middle - start + 1) {
      end = middle;
    } else {
      start = middle + 1;
    }
  }
  std::cout << "null." << std::endl;
  return 0;
}

int main() {
  std::vector<int> input = {2, 3, 1, 0, 2, 5, 3};
  auto result = duplicate(input);
  std::cout << "The duplicate element is " << result << std::endl;

  std::vector<int> input_II = {2, 3, 1, 0, 2, 5, 3};
  auto result_II = duplicate_II(input_II);
  std::cout << "The duplicate_II element is " << result_II << std::endl;
  return 0;
}

